package com.javabasic.algorithm.leetcode;

public class CountPrimes {

    /**
     * 欧拉素数  理解用：7 作为一个例子来理解
     * @param n
     * @return
     */
    public int countPrimes(int n) {
        int[] prime = new int[n];
        int[] vis = new int[n+1];
         int count = 0;
        for (int i = 2; i <= n; i++) {
            if (vis[i] == 0) {
                prime[count++] = i;
            }
            for (int j = 0; j < count && i*prime[j] <= n; j++) {
                vis[i*prime[j]] = 1;
                if (i%prime[j] == 0) break;
            }
        }
        return count;
    }
}
